#
# @lc app=leetcode.cn id=977 lang=python3
#
# [977] 有序数组的平方
#

"""
本题可以通过相向双指针来实现

nums 为一个非递减顺序排序的整数数组（包含负数），所以较大的值一定存在于数组两端
通过设置两个指针，来从数组的两端逐渐向数组中心遍历
第一种方法：
  比较左侧值平方和右侧值平方的大小，将较大的值置于新数组的末端，对应指针向中心靠拢
  共遍历 n 次即可完成
第二种方法：
  比较左侧值的[相反数]和右侧值的大小，
    a. 大于时，向新数组中置入左侧值的平方
    b. 小于等于时，向新数组中置入右侧值的平方
  该方法的优势在于每个循环只需要计算一次乘法
  
"""


# @lc code=start
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = n * [0]
        i, j = 0, n-1

        for p in range(n-1, -1, -1):
            x = nums[i] * nums[i]
            y = nums[j] * nums[j]

            if x > y:
                ans[p] = x
                i += 1
            else:
                ans[p] = y
                j -= 1
            
        return ans

# @lc code=end

